Practice | GeeksforGeeks | A computer science portal for geeks
LIVE   BATCHES
Quiz

This track of the course covers the topic "Arrays".

In details, this track will cover:

  • Arrays: What are arrays and why are they used.
  • Basic Operations: We'll look at basic array operations like insertion, deletion, and reversal.
  • Shifting and Rotation: How to shift and rotate an array.
  • Sum Arrays: How do we create a prefix sum array and when do we need it.
  • Sliding Window: Using the sliding window to improve the complexity of our program.

Objective: The objective of this track is to familiarize the learners with arrays. 

Track Content:

  • 15 Video Lectures on Arrays.
  • Theoretical Articles.
  • Progrraming practice problems.
  • 10 Quiz questions for practice.

Assessment: All Tracks in every week are associated with weekly contests.

We have combined Classroom and Theory tab and created a new Learn tab for easy access. You can access Classroom and Theory from the left panel.

An array is a collection of items of same data type stored at contiguous memory locations. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).


Arrays can be classified into two categories: 

  1. Fixed-sized arrays
  2. Dynamic-sized arrays

In this video, we discuss types of arrays in different programming languages and syntax.


Vector in C++


This video introduces ArrayList in Java.

Codes:


In this video we discuss Search and Insert operations on both fixed and dynamic sized arrays.
Codes:


In this video we discuss about Deletion operation on array. Furthur we will briefly compare arrays with other datastructures.
Codes:


This video talks about two solutions to find the largest element in an array, a O(n^2) solution and a O(n) solution.


This video talks about two solutions to find the second largest element in an array.


In this video we discuss, a function that reverse an array which takes array and size of array as parameter and returns nothing.
Codes:


This video talks about two solutions to solve the problem of moving all zeros to end keeping the order of remaining elements.


In this video we discuss a function that left rotates an array by one and takes array and size of the array as parameter and returns void.
Codes:


An element is called the leader of an array if there is no element greater than it on the right side.
Codes:


Maximum Difference problem is to find the maximum of arr[j] - arr[i] where j>i.
Codes:


In this video we discuss a naive solution to the Stock Buy and Sell Problem.
Codes:


In this video we discuss an efficient solution to the Stock Buy and Sell Problem.
Codes:


In this video, we discuss two methods(of different time and space complexity) to solve Trapping Rain Water Problem.
Codes:


Find count of maximum consecutive 1s in a binary array. Two approaches are discussed, one is O(n^2) and other is O(n). Both of these approaches require O(1) auxiliary space.
Codes:


An interesting array problem to find the length of the longest subarray that has alternating even odd elements.
Codes:


The task is to find maximum circular sum subarray of a given array.  Two approaches are discussed, one is O(n^2) and other is O(n).
Codes:


Majority element is an element that appears more than n/2 times in an array of size n. In this video, two methods to find majority element in an array are discussed.
Codes:


Given a binary array, we need to find the minimum of number of group flips to make all array elements same.  In a group flip, we can flip any set of consecutive 1s or 0s.
Codes:


Code links of the problem discussed in video
Codes:

Code links of the problem discussed in video
Codes:
 

An array is a collection of items of the same data type stored at contiguous memory locations. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).

For simplicity, we can think of an array as a fleet of stairs where on each step a value is placed (let’s say one of your friends). Here, you can identify the location of any of your friends by simply knowing the count of the step that they are on.

Remember: “Location of the next index depends on the data type that we use”.

The above image can be looked at as a top-level view of a staircase where you are at the base of the staircase. Each element can be uniquely identified by their index in the array (in a similar way where you could identify your friends by the step on which they were on in the above example).

Defining an Array: Array definition is similar to defining any other variable. There are two things that are needed to be kept in mind, the data type of the array elements and the size of the array. The size of the array is fixed and the memory for an array needs to be allocated before use, the size of an array cannot be increased or decreased dynamically.

Generally, arrays are declared as:
dataType arrayName[arraySize];

An array is distinguished from a normal variable
by brackets [ and ].

Accessing array elements: Arrays allows to access elements randomly. Elements in an array can be accessed using indexes. Suppose an array named arr stores N elements. Indexes in an array are in the range of 0 to N-1, where the first element is present at 0-th index and consecutive elements are placed at consecutive indexes. Element present at ith index in the array arr[] can be accessed as arr[i].

The below image shows an array arr[] of size 5:


Advantages of using arrays:
  • Arrays allow random access of elements. This makes accessing elements by their position faster.
  • Arrays have better cache locality that can make a pretty big difference in performance.

Examples:
// A character array in C/C++/Java
char arr1[] = {'g', 'e', 'e', 'k', 's'};

// An Integer array in C/C++/Java
int arr2[] = {10, 20, 30, 40, 50};

// Item at i'th index in array is typically accessed
// as "arr[i]". For example arr1[0] gives us 'g'
// and arr2[3] gives us 40.

Searching in an Array

Searching for an element in an array means to check if a given element is present in the array or not. This can be done by accessing elements of the array one by one starting from the first element and checking whether any of the elements matches with the given element.

We can use loops to perform the above operation of array traversal and access the elements, using indexes.

Suppose the array is named arr[] with size N and the element to be searched is referred to as key. Below is the algorithm to perform the search operation in the given array.
for(i = 0; i < N; i++)
{
if(arr[i] == key)
{
print "Element Found";
}
else
{
print "Element not Found";
}
}

Time Complexity of this search operation will be O(N) in the worst case as we are checking every element of the array from 1st to last, so the number of operations is N.

Insertion in Arrays

Given an array of a given size. The task is to insert a new element in this array. There are two possible ways of inserting elements in an array:
  1. Insert elements at the end of the array.
  2. Insert element at any given index in the array.

Special Case: A special case is needed to be considered is that whether the array is already full or not. If the array is full, then the new element can not be inserted.



Consider the given array is arr[] and the initial size of the array is N, that is the array can contain a maximum of N elements and the length of the array is len. That is, there are len number of elements already present in this array.
  • Insert an element K at end in arr[]: The first step is to check if there is any space left in the array for new element. To do this check,
    if(len < N)
    // space left
    else
    // array is full
    If there is space left for the new element, insert it directly at the end at position len + 1 and index len:
    arr[len] = k;

    Time Complexity of this insert operation is constant, i.e. O(1) as we are directly inserting the element in a single operation.
  • Insert an element K at position, pos in arr[]: The first step is to check if there is any space left in the array for new element. To do this check,
    if(len < N)
    // space left
    else
    // array is full
    Now, if there is space left, the element can be inserted. The index of the new element will be idx = pos - 1.

    Now, before inserting the element at the index idx, shift all elements from the index idx till end of the array to the right by 1 place. This can be done as:
    for(i = len-1; i >= idx; i--)
    {
    arr[i+1] = arr[i];
    }
    After shifting the elements, place the element K at index idx.
    arr[idx] = K;

    Time Complexity in worst case of this insertion operation can be linear i.e. O(N) as we might have to shift all of the elements by one place to the right.

Deletion in Arrays

To delete a given element from an array, we will have to first search the element in the array. If the element is present in the array then delete operation is performed for the element otherwise the user is notified that the array does not contains the given element.

Consider the given array is arr[] and the initial size of the array is N, that is the array can contain a maximum of N elements and the length of the array is len. That is, there are len number of elements already present in this array.

Deleting an element K from the array arr[]: Search the element K in the array arr[] to find the index at which it is present.
for(i = 0; i < N; i++)
{
if(arr[i] == K)
idx = i; return;
else
Element not Found;
}
Now, to delete the element present at index idx, left shift all of the elements present after idx by one place and finally reduce the length of the array by 1.
for(i = idx+1; i < len; i++)
{
arr[i-1] = arr[i];
}

len = len-1;

Time Complexity in worst case of this insertion operation can be linear i.e. O(N) as we might have to shift all of the elements by one place to the left.
As the term rotation signifies, array rotation means to rotate the elements of an array by given positions.

Consider the below array:

The above array is rotated counter-clockwise(towards left) by 2 elements. After rotation, the array will be:


Visually, the process of counter clock-wise array rotation(rotated by say K elements) looks like:
  • Shift all elements after K-th element to the left by K positions.
  • Fill the K blank spaces at the end of the array by first K elements from the original array.

Note: The similar approach can also be applied for clockwise array rotation.

Implementations

  • Simple Method: The simplest way to rotate an array is to implement the above visually observed approach by using extra space.
    1. Store the first K elements in a temporary array say temp[].
    2. Shift all elements after K-th element to the left by K positions in the original array.
    3. Fill the K blank spaces at the end of the original array by the K elements from the temp array.
    Say, arr[] = [1, 2, 3, 4, 5, 6, 7], K = 2
    1) Store first K elements in a temp array
    temp[] = [1, 2]
    2) Shift rest of the arr[]
    arr[] = [3, 4, 5, 6, 7, 6, 7]
    3) Store back the K elements from temp
    arr[] = [3, 4, 5, 6, 7, 1, 2]

    Time Complexity: O(N), where N is the number of elements in the array.
    Auxiliary Space: O(K) where K is the number of places by which elements will be rotated.

  • Another Method (Without extra space): We can also rotate an array by avoiding the use of temporary array. The idea is to rotate the array one by one K times.
    leftRotate(arr[], d, n)
    start
    For i = 0 to i < d
    Left rotate all elements of arr[] by one
    end

    To rotate an array by 1 position to the left:
    1. Store the first element in a temporary variable say temp.
    2. Left shift all elements after the first element by 1 position. That is, move arr[1] to arr[0], arr[2] to arr[1] and so on.
    3. Initialize arr[N-1] with temp.

    To rotate an array by K position to the left, repeat the above process K times.
    Take the same example,
    arr[] = [1, 2, 3, 4, 5, 6, 7], K = 2

    Rotate arr[] one by one 2 times.

    After 1st rotation: [2, 3, 4, 5, 6, 7, 1]
    After 2nd rotation: [ 3, 4, 5, 6, 7, 1, 2]
    Time Complexity: O(N*K), where N is the number of elements in the array and K is the number of places by which elements will be rotated.
    Auxiliary Space: O(1).

  • Juggling Algorithm: This is an extension of the above method. Instead of moving one by one, divide the array in different sets, where number of sets is equal to GCD of N and K and move the elements within sets.

    If GCD is 1 as is for the above example array (N = 7 and K = 2), then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.

    Here is an example for N = 12 and K = 3. GCD of N and K is 3:
    Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

    a) Elements are first moved in first set – (See below
    diagram for this movement)

    ArrayRotation

    arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}

    b) Then in second set.
    arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}

    c) Finally in third set.
    arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}
    Time Complexity: O(N), where N is the number of elements in the array.
    Auxiliary Space: O(1).
Reversing an array means reversing the order of elements in the given array.

Problem: Given an array of N elements. The task is to reverse the order of elements in the given array.

For Example:
Input  : arr[] = {1, 2, 3}
Output : arr[] = {3, 2, 1}

Input : arr[] = {4, 5, 1, 2}
Output : arr[] = {2, 1, 5, 4}

Iterative Solution

  • Method 1 (Using Temporary Array): The idea is to first copy all of the elements of the given array in a temporary array. Then traverse the temporary array from end and replace elements in original array by elements of temp array.

    This method will take extra space in order of O(N).
  • Method 2 (Efficient): This method is efficient then the above method and avoids using extra spaces. The idea is to traverse the array from both ends and keep swapping elements from both ends until middle of the array is reached.
    1) Initialize start and end indexes as 
    start = 0, end = N-1
    2) In a loop, swap arr[start] with arr[end]
    and change start and end as follows :
    start = start + 1,
    end = end – 1
    For Example:

    Time Complexity: O(N), where N is the number of elements in the array.

Recursive Solution

The recursive approach is almost similar to that of the method 2 of the iterative solution. Below is the recursive algorithm to reverse an array:
1) Initialize start and end indexes as 
start = 0, end = n-1
2) Swap arr[start] with arr[end]
3) Recursively call reverse for rest of the array.

Below is the recursive function to reverse an array:
void rvereseArray(arr[], start, end)
{
if (start >= end)
return;
// Swap elements at start and end
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
// Recursive Function calling
rvereseArray(arr, start + 1, end - 1);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Time Complexity: O(N), where N is the number of elements in the array.
This technique shows how a nested for loop in few problems can be converted to single for loop and hence reducing the time complexity.

Let’s start with a problem for illustration where we can apply this technique:
Given an array of integers of size 'n'.
Our aim is to calculate the maximum sum of 'k'
consecutive elements in the array.

Input : arr[] = {100, 200, 300, 400}
k = 2
Output : 700

Input : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}
k = 4
Output : 39
We get maximum sum by adding subarray {4, 2, 10, 23}
of size 4.

Input : arr[] = {2, 3}
k = 3
Output : Invalid
There is no subarray of size 3 as size of whole
array is 2.

The Naive Approach to solve this problem is to calculate sum for each of the blocks of K consecutive elements and compare which block has the maximum sum possible. The time complexity of this approach will be O(n * k).

Window Sliding Technique


The above problem can be solved in Linear Time Complexity by using Window Sliding Technique by avoiding the overhead of calculating sum repeatedly for each block of k elements.

The technique can be best understood with the window pane in bus, consider a window of length n and the pane which is fixed in it of length k. Consider, initially the pane is at extreme left i.e., at 0 units from the left. Now, co-relate the window with array arr[] of size n and plane with current_sum of size k elements. Now, if we apply force on the window such that it moves a unit distance ahead. The pane will cover next k consecutive elements.

Consider an array arr[] = {5 , 2 , -1 , 0 , 3} and value of k = 3 and n = 5

Applying sliding window technique :
  1. We compute the sum of first k elements out of n terms using a linear loop and store the sum in variable window_sum.
  2. Then we will graze linearly over the array till it reaches the end and simultaneously keep track of maximum sum.
  3. To get the current sum of block of k elements just subtract the first element from the previous block and add the last element of the current block .

The below representation will make it clear how the window slides over the array.

This is the initial phase where we have calculated the initial window sum starting from index 0 . At this stage the window sum is 6. Now, we set the maximum_sum as current_window i.e 6.


Now, we slide our window by a unit index. Therefore, now it discards 5 from the window and adds 0 to the window. Hence, we will get our new window sum by subtracting 5 and then adding 0 to it. So, our window sum now becomes 1. Now, we will compare this window sum with the maximum_sum. As it is smaller we wont the change the maximum_sum.


Similarly, now once again we slide our window by a unit index and obtain the new window sum to be 2. Again we check if this current window sum is greater than the maximum_sum till now. Once, again it is smaller so we don't change the maximum_sum.

Therefore, for the above array our maximum_sum is 6.

Given an array arr[] of size N, the task is to generate the prefix sum array of the given array.

Prefix Sum Array: The prefix sum array of any array, arr[] is defined as an array of same size say, prefixSum[] such that the value at any index i in prefixSum[] is sum of all elements from indexes 0 to i in arr[].
That is,
prefixSum[i] = arr[0] + arr[1] + arr[2] + . . . . + arr[i]

for all 0 <= i <= N.

Examples:
Input  : arr[] = {10, 20, 10, 5, 15}
Output : prefixSum[] = {10, 30, 40, 45, 60}

Explanation : While traversing the array, update
the element by adding it with its previous element.
prefixSum[0] = 10,
prefixSum[1] = prefixSum[0] + arr[1] = 30,
prefixSum[2] = prefixSum[1] + arr[2] = 40 and so on.

Below function generates a prefix sum array for a given array arr[] of size N:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX



Finding sum in a Range: We can easily calculate the sum with-in a range [i, j] in an array using the prefix sum array. Since the array prefixSum[i] stores the sum of all elements upto i. Therefore, prefixSum[j] - prefixSum[i] will give:
sum of elements upto j-th index - sum of elements upto i-th element   
The above total sum will exclude the i-th element.

Therefore, we can get the sum of elements in range [i,j] by:
prefixSum[j] - prefixSum[i-1]

The above formula will not work in the case when i = 0.

Therefore,
sumInRange = prefixSum[j]  , if i = 0

otherwise,

sumInRange = prefixSum[j] - prefixSum[i-1] , if (i != 0).


Sample Problem: Consider an array of size N with all initial values as 0. Perform given 'm' add operations from index 'a' to 'b' and evaluate highest element in array. An add operation adds 100 to all elements from index a to b (both inclusive).

Example:
Input : n = 5 // We consider array {0, 0, 0, 0, 0}
m = 3.
a = 2, b = 4.
a = 1, b = 3.
a = 1, b = 2.
Output : 300

Explanation :
After I operation -
A : 0 100 100 100 0

After II operation -
A : 100 200 200 100 0

After III operation -
A : 200 300 200 100 0

Highest element : 300

Solution using Prefix Sum:
1 : Run a loop for 'm' times, inputting 'a' and 'b'.
2 : Add 100 at index 'a' and subtract 100 from index 'b+1'.
3 : After completion of 'm' operations, compute the prefix sum array.
4 : Scan the largest element and we're done.
What we did was adding 100 at ‘a’ because this will add 100 to all elements while taking prefix sum array. Subtracting 100 from ‘b+1’ will reverse the changes made by adding 100 to elements from ‘b’ onward.

For better understanding :
After I operation -
A : 0 100 0 0 -100
Prefix Sum Array : 0 100 100 100 0

After II operation -
A : 100 100 0 -100 -100
Prefix Sum Array : 100 200 200 100 0

After III operation -
A : 200 100 -100 -100 -100
Prefix Sum Array : 200 300 200 100 0

Final Prefix Sum Array : 200 300 200 100 0

The required highest element : 300
We already have discussed the basic declaration of arrays. Arrays can also be implemented using some built-in classes available in the C++ Standard Template Library.

Some of the most commonly used classes for implementing sequential lists or arrays are:
  • Vector
  • List

Let's look at each of these classes in details.

Vector

Vector in C++ STL is a class that represents a dynamic array. The advantages of vector over normal arrays are,
  • We do not need to pass size as an extra parameter when we pass vector.
  • Vectors have many in-built functions for erasing an element, inserting an element etc.
  • Vectors support dynamic sizes, we do not have to initially specify the size of a vector. We can also resize a vector.
  • There are many other functionalities vector provide.

Vectors are same as dynamic arrays with the ability to resize itself automatically when an element is inserted or deleted, with their storage being handled automatically by the container. Vector elements are placed in contiguous storage so that they can be accessed and traversed using iterators. In vectors, data is inserted at the end. Inserting at the end takes differential time, as sometimes there may be a need of extending the array. Removing the last element takes only constant time because no resizing happens. Inserting and erasing at the beginning or in the middle is linear in time.

To use the Vector class, include the below header file in your program:
#include< vector >

Declaring Vector:
vector< Type_of_element > vector_name;

Here, Type_of_element can be any valid C++ data type,
or can be any other container also like Pair, List etc.

Some important and commonly used functions of Vector class are:
  • begin() – Returns an iterator pointing to the first element in the vector.
  • end() – Returns an iterator pointing to the theoretical element that follows the last element in the vector.
  • size() – Returns the number of elements in the vector.
  • capacity() – Returns the size of the storage space currently allocated to the vector expressed as number of elements.
  • empty() – Returns whether the container is empty.
  • push_back() – It push the elements into a vector from the back.
  • pop_back() – It is used to pop or remove elements from a vector from the back.
  • insert() – It inserts new elements before the element at the specified position.
  • erase() – It is used to remove elements from a container from the specified position or range.
  • swap() – It is used to swap the contents of one vector with another vector of same type and size.
  • clear() – It is used to remove all the elements of the vector container.
  • emplace() – It extends the container by inserting new element at position.
  • emplace_back() – It is used to insert a new element into the vector container, the new element is added to the end of the vector.

Below program illustrate the above methods:
// C++ program to illustrate the above functions
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v;
// Push elements
for (int i = 1; i <= 5; i++) v.push_back(i);
cout << "Size : " << v.size();
// checks if the vector is empty or not
if (v.empty() == false)
cout << "\nVector is not empty";
else
cout << "\nVector is empty";
cout << "\nOutput of begin and end: ";
for (auto i = v.begin(); i != v.end(); ++i) cout << *i << " ";
// inserts at the beginning
v.emplace(v.begin(), 5);
cout << "\nThe first element is: " << v[0];
// Inserts 20 at the end
v.emplace_back(20);
int n = v.size();
cout << "\nThe last element is: " << v[n - 1];
// erases the vector
v.clear();
cout << "\nVector size after erase(): " << v.size();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output:
Size : 5
Vector is not empty
Output of begin and end: 1 2 3 4 5
The first element is: 5
The last element is: 20
Vector size after erase(): 0

List

Lists are sequence containers that allow non-contiguous memory allocation. List in C++ STL implements a doubly linked list and not arrays. As compared to vector, list has slow traversal, but once a position has been found, insertion and deletion are quick. Normally, when we say a List, we talk about doubly linked lists. For implementing a singly linked list, we can use forward_list class in C++ STL.

To use the List class, include the below header file in your program:
#include< list >

Declaring List:
list< Type_of_element > list_name;

Here, Type_of_element can be any valid C++ data type,
or can be any other container also like Pair, List etc.


Some important and commonly used functions of List are:
  • front() – Returns the value of the first element in the list.
  • back() – Returns the value of the last element in the list.
  • push_front(g) – Adds a new element ‘g’ at the beginning of the list.
  • push_back(g) – Adds a new element ‘g’ at the end of the list.
  • pop_front() – Removes the first element of the list, and reduces the size of the list by 1.
  • pop_back() – Removes the last element of the list, and reduces the size of the list by 1.
  • begin() and end() – begin() function returns an iterator pointing to the first element of the list.
  • empty() – Returns whether the list is empty(1) or not(0).
  • insert() – Inserts new elements in the list before the element at a specified position.
  • reverse() – Reverses the list.
  • size() – Returns the number of elements in the list.
  • sort() – Sorts the list in increasing order.

Below program illustrate the above functions:
#include <iostream>
#include <list>
#include <iterator>
using namespace std;
//function for printing the elements in a list
void showlist(list <int> g)
{ list <int> :: iterator it; for(it = g.begin(); it != g.end(); ++it) cout << '\t' << *it; cout << '\n'; }
int main()
{
list <int> gqlist1, gqlist2;
for (int i = 0; i < 10; ++i) { gqlist1.push_back(i * 2); gqlist2.push_front(i * 3); }
cout << "\nList 1 (gqlist1) is : "; showlist(gqlist1);
cout << "\nList 2 (gqlist2) is : ";
showlist(gqlist2);
cout << "\ngqlist1.front() : " << gqlist1.front();
cout << "\ngqlist1.back() : " << gqlist1.back();
cout << "\ngqlist1.pop_front() : ";
gqlist1.pop_front();
showlist(gqlist1);
cout << "\ngqlist2.pop_back() : ";
gqlist2.pop_back();
showlist(gqlist2);
cout << "\ngqlist1.reverse() : ";
gqlist1.reverse();
showlist(gqlist1);
cout << "\ngqlist2.sort(): ";
gqlist2.sort();
showlist(gqlist2);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output:
List 1 (gqlist1) is :     0    2    4    6    
8 10 12 14 16 18

List 2 (gqlist2) is : 27 24 21 18
15 12 9 6 3 0

gqlist1.front() : 0
gqlist1.back() : 18
gqlist1.pop_front() : 2 4 6 8
10 12 14 16 18

gqlist2.pop_back() : 27 24 21 18
15 12 9 6 3

gqlist1.reverse() : 18 16 14 12
10 8 6 4 2

gqlist2.sort(): 3 6 9 12
15 18 21 24 27
Iterators are used to point at the memory addresses of STL containers. They are primarily used in a sequence of numbers, characters etc. We can use iterators to move through the contents of the container. They can be visualised as something similar to a pointer pointing to some location and we can access content at that particular location using them.

Basic Operations of iterators :-
  • begin() :- This function is used to return the beginning position of the container.
  • end() :- This function is used to return the after end position of the container.

    // C++ code to demonstrate the working of
    // iterator, begin() and end()
    #include<iostream>
    #include<iterator> // for iterators
    #include<vector> // for vectors
    using namespace std;
    int main()
    {
    vector<int> ar = { 1, 2, 3, 4, 5 };
    // Declaring iterator to a vector
    vector<int>::iterator ptr;
    // Displaying vector elements using begin() and end()
    cout << "The vector elements are : ";
    for (ptr = ar.begin(); ptr < ar.end(); ptr++)
    cout << *ptr << " ";
    return 0;
    }
    הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
    Output:
    The vector elements are : 1 2 3 4 5 
  • advance() :- This function is used to increment the iterator position till the specified number mentioned in its arguments.

    // C++ code to demonstrate the working of
    // advance()
    #include<iostream>
    #include<iterator> // for iterators
    #include<vector> // for vectors
    using namespace std;
    int main()
    {
    vector<int> ar = { 1, 2, 3, 4, 5 };
    // Declaring iterator to a vector
    vector<int>::iterator ptr = ar.begin();
    // Using advance() to increment iterator position
    // points to 4
    advance(ptr, 3);
    // Displaying iterator position
    cout << "The position of iterator after advancing is : ";
    cout << *ptr << " ";
    return 0;
    }
    הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
    Output:
    The position of iterator after advancing is : 4 
  • next() :- This function returns the new iterator that the iterator would point after advancing the positions mentioned in its arguments.
  • prev() :- This function returns the new iterator that the iterator would point after decrementing the positions mentioned in its arguments.

    // C++ code to demonstrate the working of
    // next() and prev()
    #include<iostream>
    #include<iterator> // for iterators
    #include<vector> // for vectors
    using namespace std;
    int main()
    {
    vector<int> ar = { 1, 2, 3, 4, 5 };
    // Declaring iterators to a vector
    vector<int>::iterator ptr = ar.begin();
    vector<int>::iterator ftr = ar.end();
    // Using next() to return new iterator points to 4
    auto it = next(ptr, 3);
    // Using prev() to return new iterator points to 3
    auto it1 = prev(ftr, 3);
    // Displaying iterator position
    cout << "The position of new iterator using next() is : ";
    cout << *it << " "; cout << endl;
    // Displaying iterator position
    cout << "The position of new iterator using prev() is : ";
    cout << *it1 << " ";
    cout << endl;
    return 0;
    }
    הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
    Output:
    The position of new iterator using next() is : 4 
    The position of new iterator using prev() is : 3
  • inserter() :- This function is used to insert the elements at any position in the container. It accepts 2 arguments, the container and iterator to position where the elements have to be inserted.

    // C++ code to demonstrate the working of inserter()
    #include<iostream>
    #include<iterator> // for iterators
    #include<vector> // for vectors
    using namespace std;
    int main()
    {
    vector<int> ar = { 1, 2, 3, 4, 5 };
    vector<int> ar1 = {10, 20, 30};
    // Declaring iterator to a vector
    vector<int>::iterator ptr = ar.begin();
    // Using advance to set position
    advance(ptr, 3);
    // copying 1 vector elements in other using inserter()
    // inserts ar1 after 3rd position in ar
    copy(ar1.begin(), ar1.end(), inserter(ar,ptr));
    // Displaying new vector elements
    cout << "The new vector after inserting elements is : ";
    for (int &x : ar)
    cout << x << " ";
    return 0;
    }
    הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
    Output:
    The new vector after inserting elements is : 1 2 3 10 20 30 4 5 
Arrays in Java are used to store a group of elements of same data type at contiguous memory locations.

The general form of Array declaration in Java is:
type array-name[];

OR

type[] array-name;

An array declaration has two components: the type and the name. Type declares the element type of the array. The element type determines the data type of each element that comprises the array. Like an array of type int, we can also create an array of other primitive data types such as char, float, double..etc, or user-defined data type(objects of a class). Thus, the element type for the array determines what type of data the array will hold.

For Example:
// both are valid declarations
int intArray[];
or int[] intArray;

byte byteArray[];
short shortsArray[];
boolean booleanArray[];
long longArray[];
float floatArray[];
double doubleArray[];
char charArray[];

Instantiating an Array: When an array is declared, only a reference of the array is created. To actually create or give memory to the array, you create an array like this:
array-name = new type [size];

Here,
  • type specifies the type of data being allocated.
  • size specifies the number of elements in the array.
  • array-name is the name of array variable that is linked to the array.

Example:
int intArray[];    //declaring array
intArray = new int[20]; // allocating memory to array
OR
int[] intArray = new int[20]; // combining both statements in one

Accessing Java Array Elements using for Loop: Each element in the array is accessed by its index. The index begins with 0 and ends at (total array size)-1. All the elements of array can be accessed using Java for Loop as shown below.
 
// Accessing the elements of the specified array
for (int i = 0; i < arr.length; i++)
System.out.println("Element at index " + i +
" : "+ arr[i]);

Here, arr.length gives the number of elements
present in the array named arr.

Implementation:
// Java program to illustrate creating an array of integers, puts some values in the array,
// and prints each value to standard output.
class GFG
{
public static void main (String[] args)
{
// declares an Array of integers.
int[] arr;
// allocating memory for 5 integers.
arr = new int[5];
// initialize the first elements of the array
arr[0] = 10;
// initialize the second elements of the array
arr[1] = 20;
// so on...
arr[2] = 30;
arr[3] = 40;
arr[4] = 50;
// accessing the elements of the specified array
for (int i = 0; i < arr.length; i++)
System.out.println("Element at index " + i +
" : "+ arr[i]);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output:
Element at index 0 : 10
Element at index 1 : 20
Element at index 2 : 30
Element at index 3 : 40
Element at index 4 : 50



Java also provides some inbuilt classes which can be used for implementing arrays or sequential lists. Let's look at some of these in detail.

ArrayList in Java

ArrayList is a part of the collection framework and is present in java.util package. It provides us dynamic arrays in Java. Though it may be slower than standard arrays, it can be helpful in programs where a lot of array manipulation is needed.

Constructors in Java ArrayList:
  • ArrayList(): This constructor is used to build an empty array list.
  • ArrayList(Collection c): This constructor is used to build an array list initialized with the elements from collection c.
  • ArrayList(int capacity): This constructor is used to build an array list with the specified initial capacity.

Creating a generic integer ArrayList:
ArrayList arrli = new ArrayList();

Implementation:
// Java program to demonstrate working of ArrayList in Java
import java.io.*;
import java.util.*;
class arrayli
{
public static void main(String[] args)
throws IOException
{
// size of ArrayList
int n = 5;
// declaring ArrayList with initial size n
ArrayList<Integer> arrli = new ArrayList<Integer>(n);
// Appending the new element at the end of the list
for (int i=1; i<=n; i++) arrli.add(i);
// Printing elements
System.out.println(arrli);
// Remove element at index 3
arrli.remove(3);
// Displaying ArrayList after deletion
System.out.println(arrli);
// Printing elements one by one
for (int i=0; i<arrli.size(); i++)
System.out.print(arrli.get(i)+" ");
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output:
[1, 2, 3, 4, 5]
[1, 2, 3, 5]
1 2 3 5

Click Here to learn ArrayList in Java in detail !

Vector Class in Java

The Vector class implements a growable array of objects. Vectors basically falls in legacy classes but now it is fully compatible with collections.
  • Vector implements a dynamic array that means it can grow or shrink as required. Like an array, it contains components that can be accessed using an integer index.
  • They are very similar to ArrayList but Vector is synchronized and has some legacy method, which the collection framework does not contain.
  • It extends AbstractList and implements List interfaces.

Constructor:
  • Vector(): Creates a default vector of initial capacity 10.
  • Vector(int size): Creates a vector whose initial capacity is specified by size.
  • Vector(int size, int incr): Creates a vector whose initial capacity is specified by size and the increment is specified by incr. It specifies the number of elements to allocate each time a vector is resized upwards.
  • Vector(Collection c): Creates a vector that contains the elements of collection c.

Implementation:
// Java code to illustrate Vector
import java.util.*;
class Vector_demo {
public static void main(String[] arg)
{
// Create a vector
Vector<Integer> v = new Vector<Integer>();
// Insert elements in the Vector
v.add(1);
v.add(2);
v.add(3);
v.add(4);
v.add(3);
// Print the Vector
System.out.println("Vector is " + v);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Output:
Vector is [1, 2, 3, 4, 3]

Click Here to learn Vector in Java in detail !

Problem #1 : Range Sum Queries using Prefix Sum

Description : We are given an Array of n integers, We are given q queries having indices l and r . We have to find out sum between the given range of indices.
Input 
[4, 5, 3, 2, 5]
3
0 3
2 4
1 3
Output
14 (4+5+3+2)
10 (3+2+5)
10 (5+3+2)
Solution : The numbers of queries are large. It will be very inefficient to iterate over the array and calculate the sum for each query separately. We have to devise the solution so that we can get the answer of the query in constant time. We will be storing the sum upto a particular index in prefix sum Array. We will be using the prefix sum array to calculate the sum for the given range.
prefix[] = Array stores the sum (A[0]+A[1]+....A[i]) at index i.
if l == 0 :
sum(l,r) = prefix[r]
else :
sum(l,r) = prefix[r] - prefix[l-1]

Pseudo Code
// n : size of array
// q : Number of queries
// l, r : Finding Sum of range between index l and r
// l and r (inclusive) and 0 based indexing
void range_sum(arr, n)
{
prefix[n] = {0}
prefix[0] = arr[0]
for i = 1 to n-1 :
prefix[i] = a[i] + prefix[i-1]

for (i = 1 to q )
{
if (l == 0)
{
ans = prefix[r]
print(ans)
}
else
{
ans = prefix[r] - prefix[l-1]
print(ans)
}
}
}

Time Complexity : Max(O(n),O(q))
Auxiliary Space : O(n)

Problem #2 : Equilibrium index of an array

Description - Equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. We are given an Array of integers, We have to find out the first index i from left such that -
A[0] + A[1] + ... A[i-1] = A[i+1] + A[i+2] ... A[n-1]
Input
[-7, 1, 5, 2, -4, 3, 0]
Output
3
A[0] + A[1] + A[2] = A[4] + A[5] + A[6]
Naive Solution : We can iterate for each index i and calculate the leftsum and rightsum and check whether they are equal.
for (i=0 to n-1)
{
leftsum = 0
for (j = 0 to i-1)
leftsum += arr[i]
rightsum = 0
for (j = i+1 to n-1)
rightsum += arr[i]

if leftsum == rightsum :
return i
}
Time Complexity : O(n^2)
Auxiliary Space : O(1)

Tricky Solution : The idea is to first get the total sum of array. Then Iterate through the array and keep updating the left sum which is initialized as zero. In the loop, we can get the right sum by subtracting the elements one by one. Then check whether the Leftsum and the Rightsum are equal.
Pseudo Code
// n : size of array
int eqindex(arr, n)
{
sum = 0
leftsum = 0
for (i=0 to n-1)
sum += arr[i]

for (i=0 to n-1)
{
// now sum will be righsum for index i
sum -= a[i]
if (sum == leftsum )
return i
leftsum += a[i]
}
}
Time Complexity : O(n)
Auxiliary Space : O(1)

Problem #3 : Largest Sum Subarray

Description : We are given an array of positive and negative integers. We have to find the subarray having maximum sum.
Input
[-3, 4, -1, -2, 1, 5]
Output
7
(4+(-1)+(-2)+1+5)
Solution :A simple idea is to look for all the positive contiguous segments of the array (max_ending_here is used for this), and keep the track of maximum sum contiguous segment among all the positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and if it is greater than max_so_far, update max_so_far.
Pseudo Code
//n : size of array
int largestsum(arr, n)
{
max_so_far = INT_MIN
max_ending_here = 0

for (i=0 to n-1)
{
max_ending_here += arr[i]
if max_so_far < max_ending_here :
max_so_far = max_ending_here

if max_ending_here < 0 :
max_ending_here = 0
}

return max_so_far
}
Time Complexity : O(n)
Auxiliary Space : O(1)

Problem #4 : Merge two sorted Arrays

Description : We are given two sorted arrays arr1[ ] and arr2[ ] of size m and n respectively. We have to merge these arrays and store the numbers in arr3[ ] of size m+n.
Input
1 3 4 6
2 5 7 8
Output
1 2 3 4 5 6 7 8
Solution : The idea is to traverse both the arrays simultaneously and compare the current numbers from both the Arrays. Pick the smaller element and copy it to arr3[ ] and advance the current index of the array from where the smaller element is picked. When we reach at the end of one of the arrays, copy the remaining elements of another array to arr3[ ].
Pseudo Code
// input arrays - arr1(size m), arr2(size n)
void merge_sorted(arr1, arr2, m, n)
{
arr3[m+n] // merged array
i=0,j=0,k=0
while(i < m && j < n)
{
if arr1[i] < arr2[j] :
arr3[k++] = arr1[i++]
else :
arr3[k++] = arr2[j++]
}
while(i < m)
arr3[k++] = arr1[i++]
while(j < n)
arr3[k++] = arr2[j++]
}
Time Complexity : O(m+n)
Auxiliary Space : O(m+n)
Question 1 [1 Marks]
A program P reads in 500 integers in the range [0..100] exepresenting the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies? (GATE CS 2005)
A
An array of 50 numbers
B
An array of 100 numbers
C
An array of 500 numbers
D
A dynamically allocated array of 550 numbers
Explanation

If you are facing any issue on this page. Please let us know.